package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/19 11:03
 **/

/**
 * 题目 ：粉刷房子
 * 题目详述 ：
 * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。
 * 每个房子粉刷成不同颜色的花费是以一个n x 3的正整数矩阵 costs 来表示的。
 * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2]表示第 1 号房子粉刷成绿色的花费，以此类推。
 * 请计算出粉刷完所有房子最少的花费成本。
 *
 * 提示:
 * costs.length == n
 * costs[i].length == 3
 * 1 <= n <= 100
 * 1 <= costs[i][j] <= 20
 */
public class MinCost {
    /**
     * 思路 ：
     * 即，思考：要去计算粉刷到标号为i的房子所需要的最少成本（由于相邻房子颜色不能够相同，所以还需要去考虑标记为i-1的房子的颜色）
     * a[i],即代表了当标号为i的房子粉刷颜色为红色时，其所需要的最低成本;
     * b[i],即代表了当标号为i的房子粉刷颜色为蓝色时，其所需要的最低成本;
     * c[i],即代表了当标号为i的房子粉刷颜色为绿色时，其所需要的最低成本;
     * ===> 状态转移方程 :
     * (1)a[i] = min(b[i - 1] , c[i - 1]) + costs[i][0];
     * 即，由于相邻两个房屋颜色是不能够相同的，所以需要获取下标为i-1的房子颜色为蓝色/绿色时的最低成本 + 当前下标为i房屋颜色为红色时的成本;
     * (2)b[i] = min(a[i - 1] , c[i - 1]) + costs[i][1];
     * 即，由于相邻两个房屋颜色是不能够相同的，所以需要获取下标为i-1的房子颜色为红色/绿色时的最低成本 + 当前下标为i房屋颜色为蓝色时的成本;
     * (3)c[i] = min(b[i - 1] , a[i - 1]) + costs[i][0];
     * 即，由于相邻两个房屋颜色是不能够相同的，所以需要获取下标为i-1的房子颜色为蓝色/红色时的最低成本 + 当前下标为i房屋颜色为绿色时的成本;
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {
        // 使用大小为2的数组来存储：
        // (1)a[1],用来存储（下标为i的房屋颜色为 红/蓝/绿三种颜色时，分别对应的所需要最小成本）;
        // (2)a[0],用来临时存储（根据状态转移方程，来计算下标为i+1的房屋颜色为 红/蓝/绿三种颜色时，分别对应的最小成本）;
        // ===》 需要注意的是，a[0]仅仅只是临时存储而已，经过循环之后，a[0]中所存储的数据需要转移到a[1]中：
        // 即，（后续还要通过a[1]中所存储的 && 同时根据状态转移方程），来计算下标为i+1的房屋颜色为 红/蓝/绿三种颜色时，分别对应的最小成本
        int[] a = new int[2];
        int[] b = new int[2];
        int[] c = new int[2];
        // 即，使用a[1],b[1],c[1]来存储 从0~n间房屋进行粉刷，所需要的最小成本;
        a[1] = costs[0][0];
        b[1] = costs[0][1];
        c[1] = costs[0][2];
        // 状态转移方程的隐性条件 ：i > 0
        // (即，若是i == 0时，则状态转移方程是无效的;)
        // 使用迭代代码时，为避免上述情况，即给i == 0赋值;同时，for循环遍历时，则需要从i == 1时开始进行遍历;
        for(int i = 1 ; i < costs.length ; i++){
            a[0] = Math.min(b[1] , c[1]) + costs[i][0];
            b[0] = Math.min(a[1] , c[1]) + costs[i][1];
            c[0] = Math.min(a[1] , b[1]) + costs[i][2];
            // a[0],b[0],c[0]只是用来暂时存放 从0~i号房屋粉刷不同颜色所需要的最低成本;
            // 即，当下次for循环来求取（从0~i+1号房屋粉刷某个颜色所需要的最低成本），需要使用到（从0~i号房屋粉刷不同颜色所需要的最低成本）。
            a[1] = a[0];
            b[1] = b[0];
            c[1] = c[0];
        }
        return Math.min(Math.min(a[1] , b[1]) , c[1]);
    }
}
